package com.leetcode.sorts.string;

import java.util.Arrays;

/**
 * @Author: WuPeng
 * @Date: 2021/5/31 6:04 下午
 */
public class RepeatString_459 {

    public static int[] getNext(String s) {
        int[] next = new int[s.length()];
        int j=-1;
        next[0] = j;

        for(int i=1; i<s.length(); i++){
            while(j >= 0 && s.charAt(i) != s.charAt(j+1)){
                j = next[j];
            }
            if(s.charAt(i) == s.charAt(j+1)){
                j++;
            }
            next[i] = j;
        }
        return next;
    }

    public static void main(String[] args) {
        String str = "abab";
        System.out.println(Arrays.toString(getNext(str)));
    }

}
